package leetcode.problems;

/**
 * _0402 Maximum Subarray
 * 和是最大值的连续子数组
 * Created by gmwang on 2018/3/23
 */
public class _0402MaximumSubarray {
    /**
     *    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
         For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
         the contiguous subarray [4,-1,2,1] has the largest sum = 6.

         在数组中找到连续的子数组（至少包含一个数字），这个数组的总和最大。

         例如，给定数组[2,2,-1,4,-2,2,1,-5,4]，
         连续子数组[4,-1,2,1]的sum =最大6。
     */
    /**
     * 思路：
     * 遍历，元素求和
     * sum比0小，就以当前值为sum，大于0的话，就把sum记录下来。
     * 比较sum和之前sum的值（max）
     * 较大的赋值max
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int sum = 0, max = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++) {
            sum = sum < 0? nums[i] : (sum + nums[i]);
            max = Math.max(sum, max);
        }
        return max;
    }
    public static void main(String[] args) {
        int[] x = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(x));
    }
}
